//
// Created by Semir on 2020/5/7.
//

#include <iostream>
#include <vector>
#include <map>

using namespace std;

struct TreeNode {
    int val;
    TreeNode* left;
    TreeNode* right;
    explicit TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};

TreeNode* rebuild(vector<int>& pre, vector<int>& vin, map<int, int> &indexMap, int preLeft, int preRight, int vinLeft, int vinRight) {
    if (preLeft > preRight) {
        return nullptr;
    }
    auto* root = new TreeNode(pre[preLeft]);
    int leftCnt = indexMap[pre[preLeft]] - vinLeft;
    root->left = rebuild(pre, vin, indexMap, preLeft + 1, preLeft + leftCnt, vinLeft, vinLeft + leftCnt - 1);
    root->right = rebuild(pre, vin, indexMap, preLeft + leftCnt + 1, preRight, vinLeft + leftCnt + 1, vinRight);
    return root;
}

TreeNode* reConstructBinaryTree(vector<int> pre, vector<int> vin) {
    map<int, int> indexMap;
    for (int i = 0; i < vin.size(); i++) {
        indexMap[vin[i]] = i;
    }
    return rebuild(pre, vin, indexMap, 0, pre.size() - 1, 0, vin.size() - 1);
}

void test() {
    vector<int> pre = {3, 9, 20, 15, 7};
    vector<int> vin = {9, 3, 15, 20 ,7};
    TreeNode* root = reConstructBinaryTree(pre, vin);
    cout << root->val << endl;
}

int main() {
    test();
    return 0;
}
